from collections import deque
from typing import List
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

def ladderLength(beginWord,endWord,wordList):
    #将字典中的单词存储到一个哈希表中
    word_set=set(wordList)
    #当我们的哈希表中没有元素项存在或者是尾元素不存在于哈希表中时，我们返回0
    if len(word_set)==0 or endWord not in word_set:
        return 0
    #如果开始元素在哈希表中，我们就用表中移除它
    if beginWord in word_set:
        word_set.remove(beginWord)
    #创建队列-用于广度优先遍历操作
    queue=deque()
    queue.append(beginWord)
    print(queue)
    visited=set(beginWord)
    word_len=len(beginWord)
    print(visited)    #{'h','t','i'}  #这里是用一个集合来存放这个字符串中的各个字符
    print(word_len)   #3
    step=1           #用来记录广度优先遍历的轮数
    #当queue不会空时，会继续进行下一轮循环
    while queue:
        #当前这一轮需要循环多少次
        current_size=len(queue)
        for i in range(current_size):
            #取出队列首部的元素，赋值给word
            word=queue.popleft()
            #word_list是一个列表
            word_list=list(word)
            print(word_list)
            #对word_len长度进行遍历
            for j in range(word_len):
                #属于是j中的某个元素
                origin_char=word_list[j]
                for k in range(26):
                    word_list[j]=chr(ord('a')+k)
                    print(word_list[j])
                    next_word=''.join(word_list)
                    print("next_word:",next_word)
                    if next_word in word_set:
                        #在我们的哈希表中如果存在该元素
                        if next_word==endWord:
                            return step+1
                        if next_word not in visited:
                            #如果该元素不再我们的vistied中，我们将其添加到我们下一轮要用的队列中
                            queue.append(next_word)
                            visited.add(next_word)
                word_list[j]=origin_char
        step+=1
    return 0
res=ladderLength(beginWord,endWord,wordList)
print(res)

